package strings;

/**
 * todo BM算法
 * 2个规则
 * 1.坏字符规则
 * 2.好前缀规则
 *
 * @author yeyangtao created at 16:26 2020/10/16
 */
public class BoyerMoore {
    private static final int SIZE = 256;

    /**
     * 建立散列表
     *
     * @param b  模式串
     * @param m  模式串程度
     * @param bc 散列
     */
    private void generateBC(char[] b, int m, int[] bc) {
        for (int i = 0; i < SIZE; i++) {
            bc[i] = -1;
        }
        for (int i = 0; i < m; i++) {
            int ascii = b[i];
            bc[ascii] = i;
        }
    }

    public int bm(char[] a, int n, char[] b, int m) {
        //记录模式串中每个字符最后出现的位置
        int[] bc = new int[SIZE];
        generateBC(b, m, bc);
        //i表示主串与模式串对应的第一个字符
        int i = 0;
        while (i < n - m) {
            int j;
            //从模式串最后一个元素开始匹配
            for (j = m - 1; j > 0; j--) {
                //坏字符对应模式串中的下标是j
                if (a[i + j] != b[j]) break;
            }
            if (j < 0) {
                //匹配成功返回主串与模式串匹配的字符第一个下标
                return i;
            }
            // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
            i = i + (j - bc[(int) a[i + j]]);
        }
        return -1;
    }
}
